import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Embrace
 * @version 1.0.0
 * @ClassName December.java
 * @git https://gitee.com/EmbraceQAQ
 * @createTime 2020年12月07日 11:10:00
 */
public class December {
    //    有一个二维矩阵 A 其中每个元素的值为 0 或 1 。
//    移动是指选择任一行或列，并转换该行或列中的每一个值：将所有 0 都更改为 1，将所有 1 都更改为 0。
//    在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的得分就是这些数字的总和。
//    返回尽可能高的分数。
//    示例：
//    输入：[[0,0,1,1],[1,0,1,0],[1,1,0,0]]
//    输出：39
//    解释：
//    转换为 [[1,1,1,1],[1,0,0,1],[1,1,1,1]]
//            0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39
//    提示：
//            1 <= A.length <= 20
//            1 <= A[0].length <= 20
//            A[i][j] 是 0 或 1
    public static int matrixScore(int[][] A) {
        int m = A.length;
        int n = A[0].length;
        // 先依次反转所有行，保证每行的第0列为1
        for (int i = 0; i < m; i++) {
            if (A[i][0] == 0) {
                for (int j = 0; j < n; j++) {
                    A[i][j] = 1 - A[i][j];
                }
            }
        }
        int res = 0;
        //遍历列---如果这列1的个数比0的个数小翻转
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < m; j++) {
                if (A[j][i] == 1) {
                    count++;
                }
            }
            //不是真正的翻转，记录1的个数进行后面结果返回
            if (count <= m / 2) {
                count = m - count;
            }
            //java.lang.Math.pow() 方法用于返回第一个参数的第二个参数次方。pow() 方法的返回类型为double。
            res += count * Math.pow(2, n - i - 1);
        }
        return res;
    }

    //判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
    //
    //示例 1:
    //
    //输入: 121
    //输出: true
    //示例 2:
    //
    //输入: -121
    //输出: false
    //解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
    //示例 3:
    //
    //输入: 10
    //输出: false
    //解释: 从右向左读, 为 01 。因此它不是一个回文数。
    public static boolean isPalindrome(int x) {
        //负数，尾数为零
        if(x<0||(x%10==0&&x!=0)){
            return false;
        }
        int num=0;
        while(x>num){
            //把末尾的数放到前一位，进行回文操作
            num=num*10+x%10;
            x=x/10;
        }
        //不单止要相等还有中值的情况
        return  x == num || x == num / 10;
    }
    //给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
    //
    //你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
    //
    //示例:
    //
    //给定 nums = [2, 7, 11, 15], target = 9
    //
    //因为 nums[0] + nums[1] = 2 + 7 = 9
    //所以返回 [0, 1]
    public static int[] twoSum(int[] nums, int target) {
        //遍历开始数组，排除最后一个
        for(int i=0;i<nums.length-1;i++){
            //起点为i后面一个防止重复
            for(int j=i+1;j<nums.length;j++){
                if(nums[i]+nums[j]==target){
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
    //统计所有小于非负整数 n 的质数的数量。
    //
    //示例 1：
    //
    //输入：n = 10
    //输出：4
    //解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
    //示例 2：
    //
    //输入：n = 0
    //输出：0
    //示例 3：
    //
    //输入：n = 1
    //输出：0
    //
    //
    //提示：
    //
    //0 <= n <= 5 * 106
    public static int countPrimes(int n) {
        int count =0;
        if(n<=0||n==1){
            return 0;
        }
        boolean isNum=false;
        for(int i=2;i<n;i++){
            if(i % 2 == 0 && i != 2  ) {
                continue;
            }
            isNum =true;
            for (int j = 2; j * j <= i; j++) {
                if (i % j == 0) {
                    isNum=false;
                    break;
                }
            }
            if (isNum){
                count++;
            }
        }
        return count;
    }
    //给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
    //
    //示例 1:
    //
    //输入: 123
    //输出: 321
    // 示例 2:
    //
    //输入: -123
    //输出: -321
    //示例 3:
    //
    //输入: 120
    //输出: 21
    //注意:
    //
    //假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231,  231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
    public static int reverse(int x) {
        int num=0;
        while(x!=0){
            int pop = x % 10;
            x /= 10;
            if (num > Integer.MAX_VALUE/10 || (num == Integer.MAX_VALUE / 10 && pop > Integer.MAX_VALUE % 10)) {
                return 0;
            }
            if (num < Integer.MIN_VALUE/10 || (num == Integer.MIN_VALUE / 10 && pop < Integer.MIN_VALUE % 10)) {
                return 0;
            }
            num=num*10+pop;
        }
        return num;
    }

    public static void main(String[] args) {
        December december=new December();
        december.splitIntoFibonacci("123456579");
    }

    List<Integer> ans;

    public List<Integer> splitIntoFibonacci(String S) {

        ans = new ArrayList<>();
        return dfs(0, S, 0, 0, 0) ? ans : new ArrayList<>();
    }
    /**
     * @p : 当前指针指向数组的索引
     * @s : 字符串
     * @pre1 : 前面隔一个的数
     * @pre2 : 前一个数
     * @deep : 当前是第几个数
     **/
    public boolean dfs(int p, String s, int pre1, int pre2, int deep) {
        int length = s.length();
        if (p == length) {
            return deep >= 3;
        }

        for (int i = 1; i <= 11; i++) {
            //超出长度或者以0开头直接break;
            if (p + i > length || (s.charAt(p) == '0' && i > 1)) {
                break;
            }
            //截取字符串
            String sub = s.substring(p, p + i);

            long numL = Long.parseLong(sub);
            //判断是否超出范围,或者deep不是0,1却大于他的前两个数之和
            if (numL > Integer.MAX_VALUE ||
                    (deep != 0 && deep != 1 && numL > (pre1 + pre2))) {
                break;
            }
            //转成int
            Integer num = (int) numL;
            //满足条件的数,递归加回溯
            if (deep == 0 || deep == 1 || num.equals(pre1 + pre2)) {
                ans.add(num);
                if (dfs(p + i, s, pre2, num, deep + 1)) {
                    return true;
                }
                ans.remove(num);
            }
        }
        return false;
    }

    /**
     * 有一堆石头，每块石头的重量都是正整数。
     *
     * 每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
     *
     * 如果 x == y，那么两块石头都会被完全粉碎；
     * 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
     * 最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。
     *
     *  
     *
     * 示例：
     *
     * 输入：[2,7,4,1,8,1]
     * 输出：1
     * 解释：
     * 先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
     * 再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
     * 接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
     * 最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。
     * @param stones
     * @return
     */
    public static int getStores(int[] stones) {
//        stones ={2,7,4,1,8,1};
        Arrays.sort(stones);
        if(stones.length==1){
            System.out.println(stones[0]);
            return stones[0];
        }
        int i=stones.length;
        while(stones[i - 2] != 0){
            stones[i-1]=stones[i-1]-stones[i-2];
            stones[i-2]=0;
            Arrays.sort(stones);
        }
       return stones[i-1];
    }
}
